This invention relates to encoding of data suited to error detection and correction, and more particularly this invention relates to encoding of data with a linear code or with selected linear cyclic codes whose generator polynomials can be factored. A primary example of a suitable code is a BCH code.
A BCH (Bose-Chaudhuri-Hocquenghem) code is an example of a code which can be used for correcting error bits in input data. These and other complex and powerful codes find use in satellite communication links and the like where error correction can be employed to mitigate the effects of noise interference. Such codes, however, require complex encoding and decoding algorithms. The complex encoding and decoding algorithms have typically been implemented by special-purpose computers which perform computations in real time.
As the need for very high-speed encoders has developed, the limitation of the computation technology has become apparent. Even with the most sophisticated high-speed digital logic circuits, the highest achievable data rate appears to be less than about 500 MBPS. There is nevertheless a need to develop encoders capable of supplying information in real time at rates in excess of 1 GBPS.
In order to understand the complexity of the problem, a brief explanation of the background and theory of the underlying encoding scheme is helpful. Reference may be had to works such as Berlekamp, Algebraic Coding Theory, (McGraw-Hill, 1968) or Lin & Costello, Jr., Error Control Coding, (Prentice-Hall, 1983).
A binary Bose-Chaudhuri-Hocquenghem code (or simply a BCH code) is a class of error detecting and error correcting codes having a code word length of N=2.sup.m -1 where each symbol has m bits. The generator polynomial g(x) is given by the form: EQU g(x)=1+X.sup.2 +X.sup.4 +X.sup.5 +X.sup.7 +X.sup.8 +X.sup.13 +X.sup.15 +X.sup.16 +X.sup.17 +X.sup.19 +X.sup.20 +X.sup.21 +X.sup.23 +X.sup.24
for a basic code having a code word or block length of 255 bits, of which 231 bits are information bits and 24 bits are parity check bits. The minimum distance of this code is D=7. The generator polynomial is a product of the minimum polynomials M.sub.1 (x), M.sub.3 (x), and M.sub.5 (x) of the roots .alpha., .alpha..sup.3, and .alpha..sup.5, as specified by the BCH code construction. The .alpha. is the primitive element of the Galois field, which in the case of this basic code is the Galois field GF(2.sup.8).
While the invention applies to linear error correcting codes and in specific embodiments to selected linear cyclic invariant codes whose generator polynomials can be factored, in order to simplify the explanation of the invention, the invention will be described specifically with respect to a triple-error-correcting binary BCH code. There are also special cases of BCH codes, such as Reed-Solomon codes, to which the concepts of the present invention may be applied.
The inventor wishes to call attention to the following references by way of background for the present invention. Not all of the references herein cited are necessarily prior art to the present invention.
______________________________________ Author U.S. Pat. No. Issue Date ______________________________________ Howell et al. 4,030,067 06-14-77 Takezono et al. 4,064,483 12-20-77 Chen et al. 4,142,174 02-27-79 Berlekamp 4,162,480 07-24-79 Ahamed 4,312,069 01-19-82 Koga 4,468,769 08-24-84 Kuki 4,502,141 02-26-85 Olderdissen et al. 4,556,977 12-03-85 Patterson 4,623,999 11-18-86 Koga et al. 4,694,455 09-15-87 Ozaki et al. 4,719,628 01-12-88 ______________________________________
Heretofore, virtually all BCH encoders have been based on an algorithm first described by Berlekamp, as noted in the above patent. The Berlekamp algorithm is a computation-intensive algorithm which was originally developed for relatively low-speed encoders.
The first step in the encoding computations is to compute the syndrome, or in the case of a triple-error-correcting BCH code, the three syndromes, referred to as S1, S3 and S5. There may be 24 bits in the syndromes in a typical example, which are the result of computations according to 24 parity check equations. The three syndromes are the remainders after the generator polynomial is divided by the polynomials M.sub.1 (x), M.sub.3 (x) and M.sub.5 (x).
The syndromes are the values which contain the information needed to identify and locate any errors, and the syndromes are usually computed by dividing the received polynomial by the minimum polynomials using feedback shift registers.
Implementation of an encoder circuit at high speeds of interest, namely, greater than 500 MBPS, is extremely difficult because the propagation delay of a typical flip-flop plus the propagation delay of an EXCLUSIVE OR gate plus the setup time of the next flip-flop stage in a combinatorial logic encoder must be less than 2 nanoseconds. With currently-available commercial technology, this is possible only using expensive high-speed digital GaAs circuitry. Integrated circuits operating at speeds sufficient to support computation for data rates of greater than 1 GBPS are considered impossible to realize given the current state of the art of both digital circuitry and digital microwave techniques. Even if such circuitry were available, the current state-of-the-art techniques would require that each be individually customized, thereby essentially precluding the commercial development and large-volume availability of devices incorporating a high-speed BCH encoder. Therefore, novel technology is needed to overcome the problems inherent in computation-based encoders.
The conventional technique in pattern generation for translating syndrome patterns into error locations is a two-step approach using as a first step the Berlekamp algorithm referenced above, which translates the three syndromes into three error locator polynomial coefficients, and as a second step adding an error correction word to the polynomial coefficients based on the syndromes.
The use of a Read Only memory (ROM) has been suggested by Patterson in U.S. Pat. No. 4,623,999 in connection with the realization of BCH encoders. However, ROMs have only been suggested for use in support of specialized feedback and specialized computations of the conventional encoding method without departing substantially from the conventional encoding procedure.
If all encoding computations of a 255 bit, 231 codeword (255,231) BCH code were to be stored in a Read Only Memory, the size of the memory would be 2.sup.231, or 3.4.times.10.sup.69 bits, which exceeds the storage capacity of the combination of all known computer memories. It is manifest that such an encoder is impractical. On the other hand, a computational system is far too slow for implementation at speeds in ranges exceeding about 500 MBPS.
Howell et al. describes a decoder which has an associated encoder employing a table of stored values corresponding to complete generator matrix and a complex EXCLUSIVE-OR tree. The circuitry includes certain computational tasks. The circuitry is by subsequent comparison highly redundant and thus requires the use of an excessive amount of circuitry.
Takezone is a decoder which uses cubic circuits employing Galois field arithmetic. There is no direct disclosure of encoding techniques or structures.
Chen et al. discloses a decoder for decoding Reed-Solomon codes, a special class of BCH codes. It does not disclose or suggest how to generate parity information.
Berlekamp '480 discloses a technique for generation of parity which teaches away from the invention as disclosed hereinafter. In the Berlekamp technique, the operation of multiplication, which is used to generate parity, is precomputed in Galois Field 2.sup.5 (GF(2.sup.5)) and then expressed as precomputed values in combinatorial logic, as described in Table I of the patent.
Ahamed discloses serial binary division for generating parity bits. This requires a relatively long time delay to produce the desired parity values. As a consequence there is a speed limitation based on the excessive propagation delays.
Koga and Koga et al. describe decoders. The only references to encoding are to the work of others, which appear to rely on direct computation of parity.
Kuki describes another feedback shift register approach for generating the parity associated with a BCH code. It is slowed by its propagation through a classical feedback shift register and therefore is subject to inherent speed limitations.
Olderdissen et al. describes encoding with a specialized BCH coding scheme wherein a plurality of Read Only Memory elements is employed, each of the ROMs serving unique functions. There are at least two levels of ROM-based decoding to obtain the needed parity information for encoding. The speed of the encoding process is limited by propagation time through a nibble-oriented tree structure similar to a shift register.
Ozaki describes a multiple-step parity generation technique for use in encoding a BCH code. As with other prior art, there is an inherent delay due to the multiple step processing required, thereby constraining the speed of operation.
It would be desirable to minimize the amount of memory required to solve the encoding problem without sacrificing speed of processing.
In view of the limitations in the conventional approach to the solution of the BCH encoding problem, it is apparent that what is needed is an approach to encode BCH and like codes at speeds which are not limited by the computation apparatus or conventional memory limitations.